template<class KEY, class DATA>
class avl_tree
{
protected:
	class avl_node
	{
		const KEY key;
		DATA data;
		avl_tree<KEY,DATA>::avl_node *Parent, *Right_s, *Left_s;
		int DeltaHeight, height;
		avl_node(const KEY NodeKey, DATA NodeData):key(NodeKey),data(NodeData),Parent(0),Right_s(0),Left_s(0),DeltaHieght(0),height(0){}
		~avl_node()
		{
				Parent = 0;
		}			
	};
	avl_node* root;
public:
	avl_tree():root(0){}
	virtual ~avl_tree(){}
	void updateHeight(avl_node* node);
	//void insert(const KEY NodeKey, DATA NodeData);
	//void remove(const KEY NodeKey);
	//DATA& retrive(const KEY NodeKey);
private:
	void roll(avl_node* node);
	avl_node* FindNode(const KEY NodeKey);
};


//////////////////////////////////////////////////////////////////////
//////////////////////queue starts here///////////////////////////////
//////////////////////////////////////////////////////////////////////

class queue_key{
public:
	bool operator>(const queue_key& key)
	{
		return true;
	}
	bool operator==(const queue_key& key)
	{
		return false;
	}
	bool operator<(const queue_key& key)
	{
		return false;
	}
};
template<class DATA>
class Queue:public avl_tree<queue_key,DATA>
{
protected:
	avl_node* CurrentNode; 
public:
	Queue():avl_tree(){}
	virtual ~Queue()
	{
		CurrentNode = 0;
	}
	bool moveFirst()
	{
		CurrentNode = root;
		while (CurrentNode != NULL)
		{
			if (CurrentNode->Right_s != NULL)
			{
				CurrentNode = CurrentNode->Right_s;
			}
			else
			{
				return true;
			}
		}
		return false;
	}
	//returns false in case of last node or empty tree (moves the CurrentNode to first node), otherwise returns true 
	bool moveNext()
	{
		if (CurrentNode == NULL)
		{
			return false;
		}
		if (CurrentNode->Left_s == NULL)
		{
			while (CurrentNode->Right_s != NULL)
			{
				CurrentNode = CurrentNode->Right_s;
			}
		}
		else
		{
			while(CurrentNode != root)
			{
				if (CurrentNode->Parent->Left_s == CurrentNode)
				{
					CurrentNode = CurrentNode->Parent;
					return true;
				}
				CurrentNode = CurrentNode->Parent;
			}			
		}
		moveFirst();
		return false;
	}	

	DATA& getCurrent()
	{
		if (CurrentNode != NULL)
		{
			return CurrentNode->data;
		}
		else
		{
			return *(new DATA);
		}
	}
private:	
};

template<class KEY, class DATA> 
void avl_tree<KEY,DATA>::updateHeight(avl_tree<KEY,DATA>::avl_node *node)
{
	if (node == root)
	{
		return;
	}
	if (node->Parent->height >= node->height + 1)
	{
		return;
	}
	else
	{
		node->Parent->height = node->height + 1;
		updateHeight(node->Parent);
	}

}